package leetcode.hot100;

@SuppressWarnings("all")
public class _152_乘积最大子数组 {

    /**
     * 给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），
     * 并返回该子数组所对应的乘积
     *
     * @param nums 有正数也有负数
     */
    public int maxProduct(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        int[] dpMax = new int[nums.length];
        int[] dpMin = new int[nums.length];
        dpMax[0] = nums[0];
        dpMin[0] = nums[0];
        int maxRes = nums[0];
        for (int i = 1; i < nums.length; i++) {
            // 正正=正 负负=正
            int res1 = nums[i] * dpMax[i - 1];
            int res2 = nums[i] * dpMin[i - 1];
            dpMax[i] = Math.max(Math.max(res1, res2), nums[i]);
            dpMin[i] = Math.min(Math.min(res1, res2), nums[i]);
            maxRes = Math.max(dpMax[i], maxRes);
        }
        return maxRes;
    }

}
